{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Node of a doubly linked list \n",
    "class Node: \n",
    "\tdef __init__(self, next=None, prev=None, data=None): \n",
    "\t\tself.next = next # reference to next node in DLL \n",
    "\t\tself.prev = prev # reference to previous node in DLL \n",
    "\t\tself.data = data \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Adding a node at the front of the list \n",
    "def push(self, new_data): \n",
    "\n",
    "\t# 1 & 2: Allocate the Node & Put in the data \n",
    "\tnew_node = Node(data = new_data) \n",
    "\n",
    "\t# 3. Make next of new node as head and previous as NULL \n",
    "\tnew_node.next = self.head \n",
    "\tnew_node.prev = None\n",
    "\n",
    "\t# 4. change prev of head node to new node \n",
    "\tif self.head is not None: \n",
    "\t\tself.head.prev = new_node \n",
    "\n",
    "\t# 5. move the head to point to the new node \n",
    "\tself.head = new_node \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Given a node as prev_node, insert \n",
    "# a new node after the given node \n",
    "\n",
    "def insertAfter(self, prev_node, new_data): \n",
    "\n",
    "\t\t# 1. check if the given prev_node is NULL \n",
    "\t\tif prev_node is None: \n",
    "\t\t\tprint(\"This node doesn't exist in DLL\") \n",
    "\t\t\treturn\n",
    "\n",
    "\t\t#2. allocate node & 3. put in the data \n",
    "\t\tnew_node = Node(data = new_data) \n",
    "\n",
    "\t\t# 4. Make next of new node as next of prev_node \n",
    "\t\tnew_node.next = prev_node.next\n",
    "\n",
    "\t\t# 5. Make the next of prev_node as new_node \n",
    "\t\tprev_node.next = new_node \n",
    "\n",
    "\t\t# 6. Make prev_node as previous of new_node \n",
    "\t\tnew_node.prev = prev_node \n",
    "\n",
    "\t\t# 7. Change previous of new_node's next node */ \n",
    "\t\tif new_node.next is not None: \n",
    "\t\t\tnew_node.next.prev = new_node \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add a node at the end of the DLL \n",
    "def append(self, new_data): \n",
    "\n",
    "\t\t# 1. allocate node 2. put in the data \n",
    "\t\tnew_node = Node(data = new_data) \n",
    "\t\tlast = self.head \n",
    "\n",
    "\t\t# 3. This new node is going to be the \n",
    "\t\t# last node, so make next of it as NULL \n",
    "\t\tnew_node.next = None\n",
    "\n",
    "\t\t# 4. If the Linked List is empty, then \n",
    "\t\t# make the new node as head \n",
    "\t\tif self.head is None: \n",
    "\t\t\tnew_node.prev = None\n",
    "\t\t\tself.head = new_node \n",
    "\t\t\treturn\n",
    "\n",
    "\t\t# 5. Else traverse till the last node \n",
    "\t\twhile (last.next is not None): \n",
    "\t\t\tlast = last.next\n",
    "\n",
    "\t\t# 6. Change the next of last node \n",
    "\t\tlast.next = new_node \n",
    "\t\t# 7. Make last node as previous of new node */ \n",
    "\t\tnew_node.prev = last \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
